package com.owulia.leetcode.num;

public class MaxScoreSightseeingPair {
    public int maxScoreSightseeingPair(int[] A) {
        int max = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = i + 1; j - i <= 2000 && j < A.length; j++) {
                int temp = A[i] + A[j] + i - j;
                if (temp > max) {
                    max = temp;
                }
            }
        }
        return max;
    }


    public int maxScoreSightseeingPairV2(int[] A) {
        int max = 0;
        int maxi = A[0] + 0;
        for (int i = 1; i < A.length; i++) {
            max = Math.max(max, maxi + A[i] - i);
            maxi = Math.max(maxi, A[i] + i);
        }
        return max;
    }
}
